"""
用贪心算法设计实现活动安排问题，一般背包问题，并且用不同数据量进行实验对比分析，要求分析算法的时间复杂性并且形成分析报告。
活动安排问题
n个活动场合 E={1,2,...,n}, 其中每个活动要求使用同一资源，而在同一时间内只能有一个活动使用这一资源。
每个活动都有起始时间s和结束时间f，且s<f,如果选择了活动，则在半开时间区间[s,f)内占用资源
两活动区间不相交则称两活动是相容的
要求给出在所给的活动集合中选出最大的相容的活动集合

一般背包问题
与0-1背包问题类似，不同的是在选择物品i时，可以选择物品i的一部分装入，不一定全部装入背包。
输入：背包容量c,物品个数n,对应价值v[n],重量w[n]
输出：最大价值，物品装入情况
"""
import random as rd


def EventSchedule(a, s, f, n):
    a[1] = True
    j = 1
    for i in range(2, n + 1):
        if s[i] >= f[j]:
            a[i] = True
            j = i
        else:
            a[i] = False
    # print(a)


def Sort(v, w):
    x = []
    for i in range(len(v)):
        x.append(v[i] / w[i])
    tmp = sorted(x, reverse=True)
    res = []
    for item in tmp:
        res.append(x.index(item))
    # print("res = ", res)  # 物品按价值排好序后的下标数组
    return res


def Knapsack(n, M, x, w, v):
    c = M
    # 物品按价值排好序后的下标数组tmp，tmp[i]为对应物品下标
    tmp = Sort(v, w)
    lastone = None
    maxvalue = 0
    for i in range(len(x)):
        x[i] = 0
    for i in tmp:
        if w[i] > c:
            lastone = i
            break
        else:
            x[i] = 1
            maxvalue += v[i]
            c -= w[i]
    if lastone is not None and lastone <= n:
        x[lastone] = c / w[lastone]
        maxvalue += x[lastone] * v[lastone]
    # print(x)
    return maxvalue


def Partition(a, p: int, r: int, s):
    j = r
    i = p + 1
    x = a[p]
    sx = s[p]
    while True:
        while a[i] <= x and i < r:  # a[i]<=x   左边，第一次停在a[i]>x处
            i = i + 1
        while a[j] >= x and j > p:  # a[j]>=x   右边，第一次停在a[j]<x处
            j = j - 1
        if i >= j:  # 这时如果i>=j,说明数组已经分成左右两块
            break
        a[i], a[j] = a[j], a[i]
        s[i], s[j] = s[j], s[i]
    a[p] = a[j]
    s[p] = s[j]
    a[j] = x
    s[j] = sx
    # print(a)
    return j


# 随机选取基准，改进算法
def RandomizedPartiton(a, p, r, s):
    i = rd.randint(p, r)
    a[i], a[p] = a[p], a[i]
    s[i], s[p] = s[p], s[i]
    return Partition(a, p, r, s)


def RandomizedQuickSort(a, p, r, s):
    if p < r:
        q = RandomizedPartiton(a, p, r, s)
        RandomizedQuickSort(a, p, q, s)
        RandomizedQuickSort(a, q + 1, r, s)


def runEventSchedule(n, s, f):
    a = [False] * (n + 1)
    # 按结束时间排序的非减序列
    # for i in range(len(s)):
    #     print("s:", s[i], "\tf:", f[i])
    RandomizedQuickSort(f, 0, len(f)-1, s)
    # print("after sort")
    # for i in range(len(s)):
    #     print("s:", s[i], "\tf:", f[i])
    s = [0] + s
    f = [0] + f
    EventSchedule(a, s, f, n)
    # 返回最多相容事件的列表
    return [i for i in range(len(a)) if a[i]]


def runKnapsack(n, c, w, v):
    x = [0] * (n + 1)
    w = [1] + w  # 被除数不能为0
    v = [0] + v  # 补上的数据不能干扰数据，价值0
    # 执行
    maxValue = Knapsack(n, c, x, w, v)
    return maxValue, x


if __name__ == "__main__":
    def test1():
        # 输入
        n = 11
        # a = list(range(n))
        s = [1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12]
        f = list(range(4, 15))
        n = rd.randint(10, 99)
        s = [rd.randint(0, 999) for i in range(n)]
        # s = np.empty([n], dtype=int)  # 不能被处理输入处理，不好用
        f = [x + rd.randint(1, 50) for x in s]
        print("输入：\n", n, "\n", s, f)
        # # 处理输入
        # a = [False]*(n+1)
        # s = [0] + s
        # f = [0] + f
        # EventSchedule(a, s, f, n)
        print("最多相容事件: ", runEventSchedule(n, s, f))


    def test2():
        # 输入
        # n = 3
        # c = 50
        # w = [10, 20, 30]
        # v = [60, 100, 120]
        n = rd.randint(3, 20)
        c = rd.randint(50, 200)
        w = [rd.randint(0, 999) for i in range(n)]
        v = [rd.randint(0, 999) for i in range(n)]
        print("输入：\n", n, c, w, v)
        # # 处理输入
        # x = [0]*(n+1)
        # w = [1] + w  # 被除数不能为0
        # v = [0] + v  # 补上的数据不能干扰数据，价值0
        # # 执行
        # maxValue = Knapsack(n, c, x, w, v)
        # print("x: ", x[1:], "\nmaxValue: ", maxValue)
        print("输出：\n", runKnapsack(n, c, w, v))


    test1()
    test2()
